{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "executionInfo": {
     "elapsed": 2012,
     "status": "ok",
     "timestamp": 1649954830279,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "N95QAxfi95VJ"
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "class CliffWalkingEnv:\n",
    "    \"\"\" 悬崖漫步环境\"\"\"\n",
    "    def __init__(self, ncol=12, nrow=4):\n",
    "        self.ncol = ncol  # 定义网格世界的列\n",
    "        self.nrow = nrow  # 定义网格世界的行\n",
    "        # 转移矩阵P[state][action] = [(p, next_state, reward, done)]包含下一个状态和奖励\n",
    "        self.P = self.createP()\n",
    "\n",
    "    def createP(self):\n",
    "        # 初始化\n",
    "        P = [[[] for j in range(4)] for i in range(self.nrow * self.ncol)]\n",
    "        ## 或者 P = np.zeros((self.nrow * self.ncol, 2 * 2))\n",
    "        # 4种动作, change[0]:上,change[1]:下, change[2]:左, change[3]:右。坐标系原点(0,0)\n",
    "        # 定义在左上角\n",
    "        change = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n",
    "        for i in range(self.nrow):\n",
    "            for j in range(self.ncol):\n",
    "                for a in range(4):\n",
    "                    #   位置在悬崖或者目标状态,因为无法继续交互,任何动作奖励都为0\n",
    "                    ##  最后一行是悬崖的，处在悬崖是不可能的，所以可以任意初始化 \n",
    "                    if i == self.nrow - 1 and j > 0:\n",
    "                        P[i * self.ncol + j][a] = [(1, i * self.ncol + j, 0,\n",
    "                                                    True)]\n",
    "                        continue\n",
    "                    # 其他位置\n",
    "                    ## 其他地方的下个状态，或者说下个x坐标，都要满足在格子内部，若是可能移动到网格的外部，下一步就保持不动的\n",
    "                    next_x = min(self.ncol - 1, max(0, j + change[a][0]))\n",
    "                    ## 下个状态也就是下个y坐标\n",
    "                    next_y = min(self.nrow - 1, max(0, i + change[a][1]))\n",
    "                    ## 下个状态的数组地址\n",
    "                    next_state = next_y * self.ncol + next_x\n",
    "                    ## 奖励值初始化到 -1\n",
    "                    reward = -1\n",
    "                    ##  默认没有达到终止条件（下个坐标在悬崖，或者在终点）\n",
    "                    done = False\n",
    "                    # 下一个位置在悬崖或者终点\n",
    "                    if next_y == self.nrow - 1 and next_x > 0:    ## 最后一行是悬崖的\n",
    "                        done = True    ## 达到了终止条件\n",
    "                        if next_x != self.ncol - 1:  # 下一个位置在悬崖\n",
    "                            reward = -100    ## 下个坐标是悬崖，奖励是-100\n",
    "                    ##  下一步的转移概是1，next_state是下一步的坐标，reward是动作奖励，done表示是否终止\n",
    "                    P[i * self.ncol + j][a] = [(1, next_state, reward, done)]   \n",
    "        return P\n",
    "\n",
    "class PolicyIteration:\n",
    "    \"\"\" 策略迭代算法 \"\"\"\n",
    "    def __init__(self, env, theta, gamma):\n",
    "        self.env = env\n",
    "        self.v = [0] * self.env.ncol * self.env.nrow  # 初始化价值为0\n",
    "        self.pi = [[0.25, 0.25, 0.25, 0.25]\n",
    "                   for i in range(self.env.ncol * self.env.nrow)]  # 初始化为均匀随机策略\n",
    "        self.theta = theta  # 策略评估收敛阈值\n",
    "        self.gamma = gamma  # 折扣因子\n",
    "\n",
    "    def policy_evaluation(self):  # 策略评估\n",
    "        cnt = 1  # 计数器\n",
    "        while 1:      ## 不断地循环的\n",
    "            max_diff = 0           ##  最大的不同\n",
    "            new_v = [0] * self.env.ncol * self.env.nrow             ##  状态价值函数的列表\n",
    "            for s in range(self.env.ncol * self.env.nrow):          ##  遍历所有的状态\n",
    "                qsa_list = []  # 开始计算状态s下的所有Q(s,a)价值\n",
    "                for a in range(4):  ##  遍历所有的动作，上下左右这几个方向\n",
    "                    qsa = 0         ##  动作价值初始化到0\n",
    "                    ## 遍历（s,a）对应的s转移可能，拿到状态和动作（s,a）对应的  概率、下个状态的、动作的奖励r、是否终止的\n",
    "                    ## 上述的code，对应的self.env.P[s][a]的长度都是1，也就是执行某个动作以后，该动作只能转移到某个确定的状态，不能按P转移到多个状态\n",
    "                    for res in self.env.P[s][a]:\n",
    "                        p, next_state, r, done = res        ## 状态转移概率默认=1、下个状态的、动作的奖励r(该循环内不变)、是否终止的\n",
    "                        '''\n",
    "                        根据公式来算动作价值，使用old价值函数的，当下个状态是终止条件时(1-done)=0，就不算该坐标的回报，也就是后面的部分=0\n",
    "                        本循环内部 p的累加值=1，所以p1*r+p2*r+...=(p1+p2+...)*r = r，和公式是可以对应起来的\n",
    "                        也就是贝尔曼期望方程的后半部分\n",
    "                        '''\n",
    "                        qsa += p * (r + self.gamma * self.v[next_state] * (1 - done))\n",
    "                        # 本章环境比较特殊,奖励和下一个状态有关,所以需要和状态转移概率相乘\n",
    "                    qsa_list.append(self.pi[s][a] * qsa) ##  还有一个选择动作的可能性 self.pi，每个动作的pi，对应公式贝尔曼期望方程最开始的累加部分\n",
    "                ##  累加动作价值，得到状态价值，赋值到 new 价值函数的，也就是贝尔曼期望方程最开始的累加部分\n",
    "                new_v[s] = sum(qsa_list)  # 状态价值函数和动作价值函数之间的关系\n",
    "                max_diff = max(max_diff, abs(new_v[s] - self.v[s]))  ##  old价值函数和new价值函数的绝对值差值\n",
    "            self.v = new_v   ##  复制new价值函数给old价值函数\n",
    "            ## old价值函数和new价值函数的绝对值差值很小了，< 给定的很小值 self.theta\n",
    "            if max_diff < self.theta: break  # 满足收敛条件,退出评估迭代\n",
    "            cnt += 1\n",
    "        print(\"策略评估进行%d轮后完成\" % cnt)\n",
    "\n",
    "    def policy_improvement(self):  # 策略提升\n",
    "        for s in range(self.env.nrow * self.env.ncol):          ##  遍历所有的状态\n",
    "            qsa_list = []  # 开始计算状态s下的所有Q(s,a)价值\n",
    "            for a in range(4):  ##  遍历所有的动作，上下左右这几个方向\n",
    "                qsa = 0         ##  动作价值初始化到0\n",
    "                ## 遍历（s,a）对应的s转移可能，拿到状态和动作（s,a）对应的  概率、下个状态的、动作的奖励r、是否终止的\n",
    "                ## 上述的code，对应的self.env.P[s][a]的长度都是1，也就是执行某个动作以后，该动作只能转移到某个确定的状态，不能按P转移到多个状态\n",
    "                for res in self.env.P[s][a]:\n",
    "                    p, next_state, r, done = res        ## 状态转移概率默认=1、下个状态的、动作的奖励r(该循环内不变)、是否终止的\n",
    "                    '''\n",
    "                    根据公式来算动作价值，使用old价值函数的，当下个状态是终止条件时(1-done)=0，就不算该坐标的回报，也就是后面的部分=0\n",
    "                    本循环内部 p的累加值=1，所以p1*r+p2*r+...=(p1+p2+...)*r = r，和公式是可以对应起来的\n",
    "                    也就是贝尔曼期望方程的后半部分\n",
    "                    '''\n",
    "                    qsa += p * (r + self.gamma * self.v[next_state] * (1 - done))\n",
    "                qsa_list.append(qsa)  ## 和策略评估相比较，少了状态动作选择的概率也就是没有策略了，此时选择每个动作的概率都是1\n",
    "            maxq = max(qsa_list)      ## 拿到这几个动作内最大的价值\n",
    "            ## 统计最大动作价值的个数，也就是对应的动作个数\n",
    "            cntq = qsa_list.count(maxq)  # 计算有几个动作得到了最大的Q值\n",
    "            # 让这些动作均分概率，也就是有最大动作价值的动作，其他动作价值小于最大值的动作，都被删除了也就是动作概率=0\n",
    "            self.pi[s] = [1 / cntq if q == maxq else 0 for q in qsa_list]\n",
    "        print(\"策略提升完成\")\n",
    "        return self.pi\n",
    "            \n",
    "    def policy_iteration(self):  # 策略迭代\n",
    "        while 1:\n",
    "            self.policy_evaluation()   ## 策略评估函数\n",
    "            old_pi = copy.deepcopy(self.pi)  # 将列表进行深拷贝,方便接下来进行比较\n",
    "            new_pi = self.policy_improvement()  ##  策略提升函数\n",
    "            if old_pi == new_pi: break          ##  策略不变了就可以停止迭代"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1649954831712,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "yZCGJazo95VK",
    "outputId": "c84ef7a4-7c75-42f6-92ec-bf0c3e4ea167"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "策略评估进行60轮后完成\n",
      "策略提升完成\n",
      "策略评估进行72轮后完成\n",
      "策略提升完成\n",
      "策略评估进行44轮后完成\n",
      "策略提升完成\n",
      "策略评估进行12轮后完成\n",
      "策略提升完成\n",
      "策略评估进行1轮后完成\n",
      "策略提升完成\n",
      "状态价值：\n",
      "-7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 \n",
      "-7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 \n",
      "-7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000 \n",
      "-7.458  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 \n",
      "策略：\n",
      "ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo \n",
      "ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo \n",
      "ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo \n",
      "^ooo **** **** **** **** **** **** **** **** **** **** EEEE \n"
     ]
    }
   ],
   "source": [
    "def print_agent(agent, action_meaning, disaster=[], end=[]):\n",
    "    print(\"状态价值：\")\n",
    "    for i in range(agent.env.nrow):\n",
    "        for j in range(agent.env.ncol):\n",
    "            # 为了输出美观,保持输出6个字符\n",
    "            print('%6.6s' % ('%.3f' % agent.v[i * agent.env.ncol + j]),\n",
    "                  end=' ')\n",
    "        print()\n",
    "\n",
    "    print(\"策略：\")\n",
    "    for i in range(agent.env.nrow):\n",
    "        for j in range(agent.env.ncol):\n",
    "            # 一些特殊的状态,例如悬崖漫步中的悬崖\n",
    "            if (i * agent.env.ncol + j) in disaster:\n",
    "                print('****', end=' ')\n",
    "            elif (i * agent.env.ncol + j) in end:  # 目标状态\n",
    "                print('EEEE', end=' ')\n",
    "            else:\n",
    "                a = agent.pi[i * agent.env.ncol + j]\n",
    "                pi_str = ''\n",
    "                for k in range(len(action_meaning)):\n",
    "                    pi_str += action_meaning[k] if a[k] > 0 else 'o'\n",
    "                print(pi_str, end=' ')\n",
    "        print()\n",
    "\n",
    "\n",
    "env = CliffWalkingEnv()\n",
    "action_meaning = ['^', 'v', '<', '>']\n",
    "theta = 0.001\n",
    "gamma = 0.9\n",
    "agent = PolicyIteration(env, theta, gamma)\n",
    "agent.policy_iteration()\n",
    "print_agent(agent, action_meaning, list(range(37, 47)), [47])\n",
    "\n",
    "# 策略评估进行60轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行72轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行44轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行12轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行1轮后完成\n",
    "# 策略提升完成\n",
    "# 状态价值：\n",
    "# -7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710\n",
    "# -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900\n",
    "# -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000\n",
    "# -7.458  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000\n",
    "# 策略：\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo\n",
    "# ^ooo **** **** **** **** **** **** **** **** **** **** EEEE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "executionInfo": {
     "elapsed": 3,
     "status": "ok",
     "timestamp": 1649954834592,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "qs8Xd7LI95VL"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "价值迭代一共进行14轮\n",
      "状态价值：\n",
      "-7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 \n",
      "-7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 \n",
      "-7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000 \n",
      "-7.458  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 \n",
      "策略：\n",
      "ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo \n",
      "ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo \n",
      "ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo \n",
      "^ooo **** **** **** **** **** **** **** **** **** **** EEEE \n"
     ]
    }
   ],
   "source": [
    "class ValueIteration:\n",
    "    \"\"\" 价值迭代算法 \"\"\"\n",
    "    def __init__(self, env, theta, gamma):\n",
    "        self.env = env\n",
    "        self.v = [0] * self.env.ncol * self.env.nrow  # 初始化价值为0\n",
    "        self.theta = theta  # 价值收敛阈值\n",
    "        self.gamma = gamma\n",
    "        # 价值迭代结束后得到的策略\n",
    "        self.pi = [None for i in range(self.env.ncol * self.env.nrow)]\n",
    "\n",
    "    def value_iteration(self):\n",
    "        cnt = 0\n",
    "        while 1:\n",
    "            max_diff = 0           ##  最大的不同\n",
    "            new_v = [0] * self.env.ncol * self.env.nrow             ##  状态价值函数的列表\n",
    "            for s in range(self.env.ncol * self.env.nrow):          ##  遍历所有的状态\n",
    "                qsa_list = []  # 开始计算状态s下的所有Q(s,a)价值\n",
    "                for a in range(4):  ##  遍历所有的动作，上下左右这几个方向\n",
    "                    qsa = 0         ##  动作价值初始化到0\n",
    "                    ## 遍历（s,a）对应的s转移可能，拿到状态和动作（s,a）对应的  概率、下个状态的、动作的奖励r、是否终止的\n",
    "                    ## 上述的code，对应的self.env.P[s][a]的长度都是1，也就是执行某个动作以后，该动作只能转移到某个确定的状态，不能按P转移到多个状态\n",
    "                    for res in self.env.P[s][a]:\n",
    "                        p, next_state, r, done = res        ## 状态转移概率默认=1、下个状态的、动作的奖励r(该循环内不变)、是否终止的\n",
    "                        '''\n",
    "                        根据公式来算动作价值，使用old价值函数的，当下个状态是终止条件时(1-done)=0，就不算该坐标的回报，也就是后面的部分=0\n",
    "                        本循环内部 p的累加值=1，所以p1*r+p2*r+...=(p1+p2+...)*r = r，和公式是可以对应起来的\n",
    "                        也就是贝尔曼最优方程的后半部分\n",
    "                        '''\n",
    "                        qsa += p * (r + self.gamma * self.v[next_state] * (1 - done))\n",
    "                    ## 和策略评估相比较，少了状态动作选择的概率也就是没有策略了，此时选择每个动作的概率都是1\n",
    "                    qsa_list.append(qsa)  # 这一行和下一行代码是价值迭代和策略迭代的主要区别\n",
    "                new_v[s] = max(qsa_list)      ## 拿到这几个动作内最大的价值\n",
    "                max_diff = max(max_diff, abs(new_v[s] - self.v[s]))  ##  old价值函数和new价值函数的绝对值差值\n",
    "            self.v = new_v   ##  复制new价值函数给old价值函数\n",
    "            ## old价值函数和new价值函数的绝对值差值很小了，< 给定的很小值 self.theta\n",
    "            if max_diff < self.theta: break  # 满足收敛条件,退出评估迭代\n",
    "            cnt += 1\n",
    "        print(\"价值迭代一共进行%d轮\" % cnt)\n",
    "        self.get_policy()\n",
    "\n",
    "    def get_policy(self):  # 根据价值函数导出一个贪婪策略\n",
    "        for s in range(self.env.nrow * self.env.ncol):\n",
    "            qsa_list = []  # 开始计算状态s下的所有Q(s,a)价值\n",
    "            for a in range(4):  ##  遍历所有的动作，上下左右这几个方向\n",
    "                qsa = 0         ##  动作价值初始化到0\n",
    "                ## 遍历（s,a）对应的s转移可能，拿到状态和动作（s,a）对应的  概率、下个状态的、动作的奖励r、是否终止的\n",
    "                ## 上述的code，对应的self.env.P[s][a]的长度都是1，也就是执行某个动作以后，该动作只能转移到某个确定的状态，不能按P转移到多个状态\n",
    "                for res in self.env.P[s][a]:\n",
    "                    p, next_state, r, done = res        ## 状态转移概率默认=1、下个状态的、动作的奖励r(该循环内不变)、是否终止的\n",
    "                    '''\n",
    "                    根据公式来算动作价值，使用old价值函数的，当下个状态是终止条件时(1-done)=0，就不算该坐标的回报，也就是后面的部分=0\n",
    "                    本循环内部 p的累加值=1，所以p1*r+p2*r+...=(p1+p2+...)*r = r，和公式是可以对应起来的\n",
    "                    也就是贝尔曼期望方程的后半部分\n",
    "                    '''\n",
    "                    qsa += p * (r + self.gamma * self.v[next_state] * (1 - done))\n",
    "                qsa_list.append(qsa)  ## 和策略评估相比较，少了状态动作选择的概率也就是没有策略了，此时选择每个动作的概率都是1\n",
    "            maxq = max(qsa_list)      ## 拿到这几个动作内最大的价值\n",
    "            ## 统计最大动作价值的个数，也就是对应的动作个数\n",
    "            cntq = qsa_list.count(maxq)  # 计算有几个动作得到了最大的Q值\n",
    "            # 让这些动作均分概率\n",
    "            # 让这些动作均分概率，也就是有最大动作价值的动作，其他动作价值小于最大值的动作，都被删除了也就是动作概率=0\n",
    "            self.pi[s] = [1 / cntq if q == maxq else 0 for q in qsa_list]\n",
    "\n",
    "env = CliffWalkingEnv()\n",
    "action_meaning = ['^', 'v', '<', '>']\n",
    "theta = 0.001\n",
    "gamma = 0.9\n",
    "agent = ValueIteration(env, theta, gamma)\n",
    "agent.value_iteration()\n",
    "print_agent(agent, action_meaning, list(range(37, 47)), [47])\n",
    "\n",
    "# 价值迭代一共进行14轮\n",
    "# 状态价值：\n",
    "# -7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710\n",
    "# -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900\n",
    "# -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000\n",
    "# -7.458  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000\n",
    "# 策略：\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo\n",
    "# ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo\n",
    "# ^ooo **** **** **** **** **** **** **** **** **** **** EEEE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 3,
     "status": "ok",
     "timestamp": 1649954837446,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "2ZFlb2dB95VM",
    "outputId": "0d4f2c7a-3589-4bb1-f95a-e9e4696d6201"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "冰洞的索引: {11, 12, 5, 7}\n",
      "目标的索引: {15}\n",
      "[(0.3333333333333333, 10, 0.0, False), (0.3333333333333333, 13, 0.0, False), (0.3333333333333333, 14, 0.0, False)]\n",
      "[(0.3333333333333333, 13, 0.0, False), (0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True)]\n",
      "[(0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False)]\n",
      "[(0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False), (0.3333333333333333, 13, 0.0, False)]\n"
     ]
    }
   ],
   "source": [
    "import gymnasium as gym\n",
    "env = gym.make(\"FrozenLake-v1\")  # 创建环境\n",
    "_ = env.reset(seed=0)\n",
    "env = env.unwrapped  # 解封装才能访问状态转移矩阵P\n",
    "env.render()  # 环境渲染,通常是弹窗显示或打印出可视化的环境\n",
    "\n",
    "holes = set()\n",
    "ends = set()\n",
    "for s in env.P:  ##  遍历环境的所有状态\n",
    "    for a in env.P[s]:  ##  遍历状态下所有的动作\n",
    "        for s_ in env.P[s][a]:  ##  遍历每个动作对应的转移情况\n",
    "            if s_[2] == 1.0:  # 获得奖励为1,代表是目标\n",
    "                ends.add(s_[1]) ##  终止标号的呢\n",
    "            if s_[3] == True:   ##  是否洞\n",
    "                holes.add(s_[1])  ## 标号\n",
    "holes = holes - ends\n",
    "print(\"冰洞的索引:\", holes)\n",
    "print(\"目标的索引:\", ends)\n",
    "\n",
    "## 共有三个动作的，每个动作有三种转移可能\n",
    "## 每个动作都有三种状态转移的可能，和上面的悬崖有些区别的，上面的悬崖只有一种可能\n",
    "## 导致这种情况的reason，就是冰面太滑了，可能滑到其他地方去了\n",
    "for a in env.P[14]:  # 查看目标左边一格的状态转移信息\n",
    "    print(env.P[14][a])\n",
    "\n",
    "# SFFF\n",
    "# FHFH\n",
    "# FFFH\n",
    "# HFFG\n",
    "# 冰洞的索引: {11, 12, 5, 7}\n",
    "# 目标的索引: {15}\n",
    "# [(0.3333333333333333, 10, 0.0, False), (0.3333333333333333, 13, 0.0, False),\n",
    "#  (0.3333333333333333, 14, 0.0, False)]\n",
    "# [(0.3333333333333333, 13, 0.0, False), (0.3333333333333333, 14, 0.0, False),\n",
    "#  (0.3333333333333333, 15, 1.0, True)]\n",
    "# [(0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True),\n",
    "#  (0.3333333333333333, 10, 0.0, False)]\n",
    "# [(0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False),\n",
    "#  (0.3333333333333333, 13, 0.0, False)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 7,
     "status": "ok",
     "timestamp": 1649954839116,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "4gf_IaeZ95VM",
    "outputId": "20ba5b95-4481-4b40-8015-54ea7fa0c2cb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "策略评估进行25轮后完成\n",
      "策略提升完成\n",
      "策略评估进行58轮后完成\n",
      "策略提升完成\n",
      "状态价值：\n",
      " 0.069  0.061  0.074  0.056 \n",
      " 0.092  0.000  0.112  0.000 \n",
      " 0.145  0.247  0.300  0.000 \n",
      " 0.000  0.380  0.639  0.000 \n",
      "策略：\n",
      "<ooo ooo^ <ooo ooo^ \n",
      "<ooo **** <o>o **** \n",
      "ooo^ ovoo <ooo **** \n",
      "**** oo>o ovoo EEEE \n"
     ]
    }
   ],
   "source": [
    "# 这个动作意义是Gym库针对冰湖环境事先规定好的\n",
    "action_meaning = ['<', 'v', '>', '^']   ## 上下左右的标识符\n",
    "theta = 1e-5   ## 当绝对值差值小于阀值时，停止迭代的呢\n",
    "gamma = 0.9    ## γ值\n",
    "agent = PolicyIteration(env, theta, gamma)  ## 实例化策略迭代\n",
    "agent.policy_iteration()      ## 迭代\n",
    "print_agent(agent, action_meaning, [5, 7, 11, 12], [15]) ## 输出\n",
    "\n",
    "# 策略评估进行25轮后完成\n",
    "# 策略提升完成\n",
    "# 策略评估进行58轮后完成\n",
    "# 策略提升完成\n",
    "# 状态价值：\n",
    "#  0.069  0.061  0.074  0.056\n",
    "#  0.092  0.000  0.112  0.000\n",
    "#  0.145  0.247  0.300  0.000\n",
    "#  0.000  0.380  0.639  0.000\n",
    "# 策略：\n",
    "# <ooo ooo^ <ooo ooo^\n",
    "# <ooo **** <o>o ****\n",
    "# ooo^ ovoo <ooo ****\n",
    "# **** oo>o ovoo EEEE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 6,
     "status": "ok",
     "timestamp": 1649954839117,
     "user": {
      "displayName": "Sam Lu",
      "userId": "15789059763790170725"
     },
     "user_tz": -480
    },
    "id": "cqPm4jxd95VN",
    "outputId": "ab6bdc64-5a4a-47f0-c6af-08bf4c2aeb0f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "价值迭代一共进行60轮\n",
      "状态价值：\n",
      " 0.069  0.061  0.074  0.056 \n",
      " 0.092  0.000  0.112  0.000 \n",
      " 0.145  0.247  0.300  0.000 \n",
      " 0.000  0.380  0.639  0.000 \n",
      "策略：\n",
      "<ooo ooo^ <ooo ooo^ \n",
      "<ooo **** <o>o **** \n",
      "ooo^ ovoo <ooo **** \n",
      "**** oo>o ovoo EEEE \n"
     ]
    }
   ],
   "source": [
    "action_meaning = ['<', 'v', '>', '^']   ## 上下左右的标识符\n",
    "theta = 1e-5   ## 当绝对值差值小于阀值时，停止迭代的呢\n",
    "gamma = 0.9    ## γ值\n",
    "agent = ValueIteration(env, theta, gamma)  ## 实例化价值迭代\n",
    "agent.value_iteration()      ## 迭代\n",
    "print_agent(agent, action_meaning, [5, 7, 11, 12], [15]) ## 输出\n",
    "\n",
    "# 价值迭代一共进行60轮\n",
    "# 状态价值：\n",
    "#  0.069  0.061  0.074  0.056\n",
    "#  0.092  0.000  0.112  0.000\n",
    "#  0.145  0.247  0.300  0.000\n",
    "#  0.000  0.380  0.639  0.000\n",
    "# 策略：\n",
    "# <ooo ooo^ <ooo ooo^\n",
    "# <ooo **** <o>o ****\n",
    "# ooo^ ovoo <ooo ****\n",
    "# **** oo>o ovoo EEEE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "第4章-动态规划算法.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
